﻿#include <bits/stdc++.h>
#include <omp.h>
using namespace std;

typedef struct point {
	int pst1, pst2; //起点
	int pend;        //终点
	double weight;  //该节点的权重+
	int cnt;        //节点的编号
	int kind;       //节点的种类
};
/*
	二链存放编号及其对应的二链
	三链往上求出之后，输出，更新cob;
*/
struct Bit {//当前编号下，生成链的组合，例如选择1，2，3 可生成的三链
	int ser_num;//当前编号
	vector<vector<int> > p;//此编号下生成链的组合
	set<string>p_ser;//对p里面的所有链进行唯一编号，插入新的链时查找p_ser，实现去重
};
struct Psi {
	vector<int>numbers;
	int ct;
};
vector<Psi>psi;
void print(vector<Bit> sk, int sum_cnt, string dastring);
string trans(int tmp);
//clock_t sta1, end1;
vector<Bit> cob;//cod当前k-1链
point* p = new point[1000];  //存储节点
int num = 0;     //节点个数
vector<string> twoChain;    //存放二链
vector<int> m;
vector<int> twoChaintmp;         //临时存放组成链的二链序号
map<string, double> twoChainmp;       //存放二链，求出对应二链的权重，便于使用
map<string, int> twoChainlist;        //存放二链，同时对二链编号，便于使用
map<int, string> twoChainlist_res;
map<string, int>kChainlist;
map<int, vector<int>>MyListView;//存储二链对应的节点
vector<int> k_n[100000];//存储n个数取k个数所有的组合
int n;
//找到vector下指定的下标
int find_Vector_cnt(int a) {
	for (int i = 0; i < psi.size(); i++) {
		if (psi[i].ct == a) {
			return i;
		}
	}
	return -1;
}
//删除指定节点，得到k-1个数的组合的节点
vector<int> ReMove(vector<int>a, int tmp) {
	vector<int>b;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != tmp) {
			b.push_back(a[i]);
		}
	}
	return b;
}
//获取当前选择的节点们的编号
int ObtainSeri(vector<int>a) {
	sort(a.begin(), a.end());
	int sum = 0;
	for (int i = 0; i < a.size(); i++) {
		sum += pow(2,a[i]-1);
	}
	return sum;
}
//打印统计信息
void printWei(map<string, int>textMap, string dastring) {
	ofstream fout(dastring);
	map<string, int>::iterator it;
	it = textMap.begin();
	int sum = 0;
	while (it != textMap.end()) {
		fout << it->first << "    " << it->second << endl;
		sum += it->second;
		it++;
	}
	fout << "    " << sum << endl;
}
set<int> findCntBackVec(vector<int>tp) {
	set<int>tp_back;
	for (int i = 0; i < tp.size(); i++) {
		for (int j = 0; j < MyListView[tp[i]].size(); j++) {
			tp_back.insert(MyListView[tp[i]][j]);
		}
	}
	return tp_back;
}
//打印vector<Bit>（k链）
void print(vector<Bit>sk, int sum_cnt, string dastring) {
	ofstream fout(dastring);
	string castring = "wei_" + trans(sum_cnt) + ".txt";
	map<string, int>kChainlistTmp;
	map<string, int>::iterator it,ti;
	vector<int>tmp_Two_Vec;
	for (int i = 0; i < sk.size(); i++) {
		for (int j = 0; j < sk[i].p.size(); j++) {
			vector<int>tmp_Two_Vect_Tmp;
			vector<int>MyVectorTmp;
			set<int>tmp_Two;
			double weight = 0;

			for (int k = 0; k < sk[i].p[j].size(); k++) {
				weight += twoChainmp[twoChainlist_res[sk[i].p[j][k]]];
				fout << sk[i].p[j][k] << "    ";		
				MyVectorTmp.push_back(sk[i].p[j][k]);
			}
			int wei = ((weight / sk[i].p[j].size() + 0.0005) * 1000);
			double wei2 = (double)wei / 1000;
			string weiTmp = to_string(wei2);
			fout << "    ";
			fout << weiTmp << "    ";
			tmp_Two = findCntBackVec(MyVectorTmp);
			if (tmp_Two_Vec.empty()) {
				
				tmp_Two_Vec.assign(tmp_Two.begin(), tmp_Two.end());
				for (int z = 0; z < tmp_Two_Vec.size(); z++) {
					fout << tmp_Two_Vec[z] << " ";
				}
		
			}
			else {
				tmp_Two_Vect_Tmp.assign(tmp_Two.begin(), tmp_Two.end());
				int flag = 0;
				for (int u = 0; u < tmp_Two_Vect_Tmp.size(); u++) {
					if (tmp_Two_Vec[u] != tmp_Two_Vect_Tmp[u]) {
						flag = 1;
					}
				}
				if (flag == 1) {
					for (int z = 0; z < tmp_Two_Vect_Tmp.size(); z++) {
						fout << tmp_Two_Vect_Tmp[z] << " ";
					}
					tmp_Two_Vec.clear();
					tmp_Two_Vec = tmp_Two_Vect_Tmp;
				}
			}
			fout << endl;
			
			
			//k-all
			ti = kChainlistTmp.find(weiTmp);
			if (ti == kChainlistTmp.end()||kChainlistTmp.empty()) {
				kChainlistTmp.insert(pair<string, int>(weiTmp, 1));
			}
			else {
				ti->second++;
			}
			//all
			it = kChainlist.find(weiTmp);
			if (it == kChainlist.end()||(kChainlist.empty())) {
				kChainlist.insert(pair<string, int>(weiTmp, 1));
			}
			else {
				it->second++;
			}

		}		
	}
	printWei(kChainlistTmp, castring);
	kChainlistTmp.clear();
}
bool find(vector<int>sg, int intTmp) {
	for (int i = 0; i < sg.size(); i++) {
		if (sg[i] == intTmp) {
			return true;
		}
	}
	return false;
}
//将数字转换成字符串
string trans(int a) {
	char ans[100];
	int k = 0;
	while (a > 0) {
		int t = a % 10;
		a /= 10;
		char tmp = '0' + t;
		ans[k++] = tmp;
	}
	for (int i = 0; i < k / 2; i++) {
		int t = ans[i];
		ans[i] = ans[k - i - 1];
		ans[k - i - 1] = t;
	}
	string s;
	s.assign(ans, k);

	return s;
}
//p_ser实现
string p_serCalculate(vector<int>p_tmp) {
	string sum = "";
	sort(p_tmp.begin(), p_tmp.end());
	for (int i = 0; i < p_tmp.size(); i++) {
		if (i == 0) {
			sum += trans(p_tmp[i]);
		}
		else {
			sum += "," + trans(p_tmp[i]);
		}
	}
	return sum;
}
//读取文件F.xlx和S.xlx
int Read() {
	FILE* fpf, * fps;
	//读取F.xlx文件
	fpf = fopen("C:\\programming\\pro\\F.xls", "r");
	while (!feof(fpf)) {
		p[num].cnt = num + 1;
		double pst1, pend;
		fscanf(fpf, "%lf", &pst1);
		fseek(fpf, 1L, SEEK_CUR);
		fscanf(fpf, "%lf", &pend);
		fseek(fpf, 1L, SEEK_CUR);
		fscanf(fpf, "%lf", &p[num].weight);
		p[num].pst1 = (int)pst1;
		p[num].pst2 = (int)pst1;
		p[num].pend = (int)pend;
		p[num].kind = 0;
		num++;
	}
	num--;	
	////读取S.xlx文件
	//fps = fopen("C:\\programming\\pro\\S.xls", "r");
	//while (!feof(fps)) {
	//	p[num].cnt = num + 1;
	//	double pst1, pst2, pend;
	//	fscanf(fps, "%lf", &pst1);
	//	fseek(fps, 1L, SEEK_CUR);
	//	fscanf(fps, "%lf", &pst2);
	//	fseek(fps, 1L, SEEK_CUR);
	//	fscanf(fps, "%lf", &pend);
	//	fseek(fps, 1L, SEEK_CUR);
	//	fscanf(fps, "%lf", &p[num].weight);
	//	p[num].pst1 = (int)pst1;
	//	p[num].pst2 = (int)pst2;
	//	p[num].pend = (int)pend;
	//	p[num].kind = 1;
	//	num++;
	//}
	/*num--;*/
	return num;
}
//确定是否有此编号下的k链
bool is_ex(int serNum, int& where) {
	for (int i = 0; i < cob.size(); i++) {
		if (cob[i].ser_num == serNum) {
			where = i;
			return 1;
		}
	}
	return 0;
}
//求二链
void find_TwoChain() {

	int numTwoChain = 0;
	int numz = 0;
	int cg = 0;
	/*
		 运用了集合之间的关系
		 ∩ 之后有元素，说明两集合有共同的元素
		 同时得到共同的元素
	*/
	for (int i = 0; i < num - 1; i++) {
		for (int j = i + 1; j < num; j++) {
			set<int>s1;//存储节点1的指标            
			set<int>s2;//存储节点2的指标
			set<int>c;//s1和s2交集
			double weight = (p[i].weight + p[j].weight) / 2;
			string tmp1 = trans(p[i].cnt);
			string tmp2 = trans(p[j].cnt);
			string tmp = "r" + tmp1 + "r" + tmp2;
			string tmps = "r" + tmp2 + "r" + tmp1;
			if (p[i].cnt != p[j].cnt && p[i].kind == 0 && p[j].kind == 0 && p[i].cnt != 0 && p[j].cnt != 0) {
				s1.insert(p[i].pst1); s1.insert(p[i].pend);
				s2.insert(p[j].pst1); s2.insert(p[j].pend);
			}
			else if (p[i].cnt != p[j].cnt && p[i].kind == 1 && p[j].kind == 1 && p[i].cnt != 0 && p[j].cnt != 0) {
				s1.insert(p[i].pst1); s1.insert(p[i].pst2); s1.insert(p[i].pend);
				s2.insert(p[j].pst1); s2.insert(p[j].pst2); s2.insert(p[j].pend);
			}
			else if (p[i].cnt != p[j].cnt && p[i].kind == 0 && p[j].kind == 1 && p[i].cnt != 0 && p[j].cnt != 0) {
				s1.insert(p[i].pst1); s1.insert(p[i].pend);
				s2.insert(p[j].pst1); s2.insert(p[j].pst2); s2.insert(p[j].pend);
			}
			else if (p[i].cnt != p[j].cnt && p[i].kind == 1 && p[j].kind == 0 && p[i].cnt != 0 && p[j].cnt != 0) {
				s1.insert(p[i].pst1); s1.insert(p[i].pst2); s1.insert(p[i].pend);
				s2.insert(p[j].pst1); s2.insert(p[j].pend);
			}
			set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(c, c.begin()));//求交集
			if (!c.empty()) {
				int cz = pow(2,p[i].cnt-1) + pow(2,p[j].cnt-1);
				twoChain.push_back(tmp);
				twoChain.push_back(tmps);
				twoChainmp.insert(pair<string, double>(tmp, weight));
				twoChainmp.insert(pair<string, double>(tmps, weight));
				twoChainlist.insert(pair<string, int>(tmp, cz));
				twoChainlist.insert(pair<string, int>(tmps, cz));
				twoChainlist_res.insert(pair<int, string>(cz, tmp));
				twoChainlist_res.insert(pair<int, string>(cz, tmps));
				numTwoChain++;
				cout << cz << "    " << tmp << endl;
				vector<int>pp;
				pp.push_back(p[i].cnt);
				pp.push_back(p[j].cnt);
				
				int serg = ObtainSeri(pp);
				MyListView.insert(pair<int, vector<int>>(serg, pp));
				pp.clear();
				pp.push_back(cz);
				Bit bitTmp;
				bitTmp.ser_num = serg;
				bitTmp.p.push_back(pp);
				cob.push_back(bitTmp);
				cg++;
			}
		}
	}
	print(cob, 2, "data_2.txt");//将二链输出到data_2.txt
}
//n个数取其中k个，结果存放在
int testCombination(vector<int> set, int n, int k) {
	vector<int> p;
	p.insert(p.end(), k, 1);
	p.insert(p.end(), n - k, 0);
	int cot = 0;
	do {
		vector<int> vec;
		int j = 0;
		for (int i = 0; i != p.size(); ++i) {
			if (p[i]) {
				vec.push_back(set[i]);
				j++;
			}
		}
		k_n[cot] = vec;
		cot++;

	} while (prev_permutation(p.begin(), p.end()));
	return cot;
}
//生成幂集
vector<vector<int> > subsets(vector<int>& S) {
	vector<vector<int> > res(1);
	sort(S.begin(), S.end());
	for (int i = 0; i < S.size(); ++i) {
		int size = res.size();
		for (int j = 0; j < size; ++j) {
			res.push_back(res[j]);
			res.back().push_back(S[i]);
		}
	}
	return res;
}
//查找对应编号下的Bit，获取Bit
void findBit(int serBit, int intTmp, vector<int>leftmp, int &is_t, vector<Bit>& tpod, int where,int xuhao,int kk) {
	int fl = 0;
	Bit bitTmp = cob[where];
	set<int>createdTwoChain;//存储生成的二链的编号
	vector<int>createdTwoChain_vec;
	vector<vector<int> >createdPowSet;//存储生成集合的幂集合
	if (bitTmp.ser_num == serBit) {
		
		for (int k = 0; k < leftmp.size(); k++) {//遍历当前情况下的组成k-1链的二链编号
			string stmp = "r" + trans(leftmp[k]) + "r" + trans(intTmp);
			map<string, int>::iterator it;
			it = twoChainlist.find(stmp);//发现可以构成二链
			if (it != twoChainlist.end()) {
				int ls_cnt = twoChainlist[stmp];//获取此二链的编号
				createdTwoChain.insert(ls_cnt);//加入到集合  
			}
		}

		if (createdTwoChain.empty()) {
			is_t = 1;
			return;
		}

		createdTwoChain_vec.assign(createdTwoChain.begin(), createdTwoChain.end());

		leftmp.push_back(intTmp);
		int xuhao = ObtainSeri(leftmp);

		createdPowSet = subsets(createdTwoChain_vec);//所有新的二链生成的幂集
		
		for (int j = 0; j < bitTmp.p.size(); j++) { //遍历当前编号下的k-1链的不同情况
			if (bitTmp.p[j].size() == 0) {
				continue;
			}
			set<int>vecTmp(bitTmp.p[j].begin(), bitTmp.p[j].end());
			//cout << endl;
			for (int h = 0; h < createdPowSet.size(); h++) {
				set<int>tmp_vecTmp = vecTmp;
				Bit bit_tmp;
				//if (createdPowSet[h].size() > 0) {
					
					//cout << "createdPowSet : ";
				//}
				if (createdPowSet[h].size() == 0) {
					continue;
				}
				for (int g = 0; g < createdPowSet[h].size(); g++) {//遍历幂集合，和已有k-1链组合
					tmp_vecTmp.insert(createdPowSet[h][g]);//将新生成二链编号加入到当前情况下的组成k-1链的二链编号中,
					//cout << createdPowSet[h][g] << " ";
				}
				vector<int>v_vecTmp;
				v_vecTmp.assign(tmp_vecTmp.begin(), tmp_vecTmp.end());
				
				int flag = 1, flag2 = 1;
				if (v_vecTmp.size() < kk - 1) {
					tmp_vecTmp.clear();
					continue;
				}
				//cout << "v_vecTmp1 : ";
				//for (int iii = 0; iii < v_vecTmp.size(); iii++) {
					//cout << v_vecTmp[iii] << " ";
				//}
				//cout << endl;
				string p_serSum = p_serCalculate(v_vecTmp);
				
				for (int f = 0; f < tpod.size(); f++) {
					set<string>::iterator it;
					it = tpod[f].p_ser.find(p_serSum);
					if (xuhao == tpod[f].ser_num) {
						/*set<int>::iterator it;
						it = tpod[f].p_ser.find(p_serSum);*/
						if (it != tpod[f].p_ser.end()) {
							flag2 = 0;
							flag = 0;
							break;
						}
						
						if (flag2 == 1) {

							tpod[f].p.push_back(v_vecTmp);
							tpod[f].p_ser.insert(p_serSum);
							flag = 0;
							break;
						}
					}
				}
				if (flag == 1) {
					bit_tmp.ser_num = xuhao;
					bit_tmp.p.push_back(v_vecTmp);
					bit_tmp.p_ser.insert(p_serSum);
					tpod.push_back(bit_tmp);
					
				}
				tmp_vecTmp.clear();

			}
		}


	}

	//}
}
void solve() {
	string dastring = "data_";//写入的文件名
	for (int k = 3; k <= n; k++) {//n个数中取i个
		vector<vector<Bit>>sod;//二维存储每个线程求取当前k链
		cout << "k = " << k << endl;
		int cnt = testCombination(m, n, k);//cnt返回组合数量		
		dastring += trans(k) + ".txt";//更新文件名
		sod.resize(100000000);
		int j = 0,i = 0;
		vector<int>tmp;
#pragma omp parallel for private(j) schedule(dynamic) num_threads(2)
		for (i = 0; i < cnt; i++) {
			int num_Tmp;
			/*int my_rank = omp_get_thread_num();
			int thread_count = omp_get_num_threads();
			printf("id = %d of %d\n", my_rank, thread_count);*/


			tmp = k_n[i];
			for (j = 0; j < tmp.size(); j++) {
				vector<int>leftmp = ReMove(tmp, tmp[j]);//存储k-1链的组合

				sort(leftmp.begin(), leftmp.end());
				int serNum = ObtainSeri(leftmp);
				int xuhao = ObtainSeri(tmp);
				int is_t = 0;
				int where;
				if (is_ex(serNum, where)) {
					//cout << "tmp : ";
					//for (int ii = 0; ii < tmp.size(); ii++) {
						//cout << tmp[ii] << " ";
					//}
					//cout << endl;
					findBit(serNum, tmp[j], leftmp, is_t, sod[i], where,xuhao,k);
					if (is_t == 1) {
						break;
					}
				}
			}
		}
		cob.clear();
#pragma omp master
		{
			for (i = 0; i < sod.size(); i++) {

				for (j = 0; j < sod[i].size(); j++) {
					cob.push_back(sod[i][j]);
					
				}
				//sod[i].clear();
			}
		}

		print(cob, k, dastring);
		//sod.clear();
		dastring = "data_";
	}
}
int main()
{
	n = Read();
	printf("n = %d\n", n);
	for (int i = 0; i < n; i++) {
		m.push_back(i + 1);
	}
	//找到二链
	find_TwoChain();
	int num = 0;
	solve();
	printWei(kChainlist, "wei_all.txt");
	return 0;
}
//给定存储二链编号的vector，获取构成这些二链的节点，返回为vector
//vector<int> findCnt(vector<int>a) {
//	set<int>tmpSet;
//	for (int i = 0; i < a.size(); i++) {
//		map<int, string>::iterator it;//遍历指针it
//		it = twoChainlist_res.find(a[i]);
//		if (it != twoChainlist_res.end()) {//存在此二链
//			string stringTmp = twoChainlist_res[a[i]];//得到此二链对应的字符串
//			for (int j = 0; j < stringTmp.length(); j++) {//从此字符串中找到节点（"r"+节点+"r"+节点)
//				if (stringTmp[j] != 'r') {
//					int itmp = 0;
//					for (int z = j; z <= stringTmp.length(); z++) {
//						if (stringTmp[z] == 'r' || z == stringTmp.length()) {
//							tmpSet.insert(itmp);
//							j = z;
//							break;
//						}
//						else {
//							itmp = itmp * 10 + (stringTmp[z] - '0');
//						}
//					}
//				}
//			}
//		}
//	}
//	vector<int>vecTmp;
//	vecTmp.assign(tmpSet.begin(), tmpSet.end());//将set转换成vector
//	return vecTmp;
//}